package com.wdc.queue;

//数组实现大顶堆
@SuppressWarnings("all")
public class PrioritryQueue4<E extends Priority> implements  Queue<E>{



    Priority[] array;
    int size;

    public PrioritryQueue4(int capacity) {
        array = new Priority[capacity];

    }


    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (parent >= 0 && array[parent].priority() < value.priority()){
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = value;
        return true;
    }

    /*
    1.交换堆顶和尾部元素，让尾部元素出队
    2. (下潜）
         - 从堆顶开始，将父元素与两个子孩子间较大者交换
         - 直到父类元素大于两个孩子，或者没有孩子为止
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0,size-1);
        size--;
        Priority e = array[size];
        array[size] = null;  //help GC

        //下潜

        return (E) e;
    }

    private void down(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        int max = parent;  //假设父节点的优先级是最大值
        if (left < size && array[left].priority() > array[max].priority()){
            max = left;
        }
        if (right < size && array[right].priority() > array[max].priority()){
            max = right;
        }

        if (max!= parent){
            swap(parent,max);
            down(max);
        }

    }

    private void swap(int i, int j) {
        Priority tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;


    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }


        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
